package org.example.dfs;

/**
 * @author liyishan
 * @date 2023/9/4 09:24
 * @apiNote
 */

public class Test00079Exist {
    public static void main(String[] args) {
        char[][] board = new char[][]{{'a','a'},{'a','a'}};
        String word = "aaa";
        System.out.println(exist(board,word));
    }


    public static boolean exist(char[][] board, String word) {
        int h = board.length;
        int w = board[0].length;
        boolean[][] visited = new boolean[h][w];
        for(int i =0;i<h;i++){
            for(int j = 0;j<w;j++){
                boolean flag = dfs(board,visited,i,j,word,0);
                if(flag){
                    return true;
                }
            }
        }
        return false;
    }

    public static boolean dfs(char[][] board,boolean[][] visited,int i,int j,String word,int index){
        if(board[i][j] !=word.charAt(index)){
            return false;
        }else if(index == word.length()-1){
            return true;
        }
        visited[i][j] = true;
        int[][] directions = {{0,1},{0,-1},{1,0},{-1,0}};
        boolean result = false;
        for(int[] dir:directions){
            int newi = i+dir[0];
            int newj = j+dir[1];
            if(newi>=0 && newi<board.length && newj>=0 && newj<board[0].length){
                if(!visited[newi][newj]){
                    boolean flag = dfs(board,visited,newi,newj,word,index+1);
                    if(flag){
                        result =  true;
                        break;
                    }
                }
            }
        }
        visited[i][j] = false;
        return result;
    }
}
